package com.demo.datastructure.tree;

/**
 * @description: 二叉查找树示例
 * @author: ljr
 * @create: 2022/1/22 10:49 AM
 */
public class MyBinarySearchTree1<Key extends Comparable<Key>, Value> {

    private Node root;

    private int i;

    private int y;

    public int size(){
       return size(root);
    }

    private int size(Node node){
        if(node == null) return 0;
        return node.n;
    }


    public Node find(Key key){
        return findV(root, key);
    }

    private Node find(Node parent, Key key){
        if(parent == null) return null;
        int cmp = parent.key.compareTo(key);
        if(cmp == 0){
            return parent;
        }else if(cmp == 1){
            return find(parent.left, key);
        }else{
            return find(parent.right, key);
        }
    }

    private Node findV(Node parent, Key key){
        while(parent != null){
            int cmp = parent.key.compareTo(key);
            if(cmp == 1){
                parent = parent.left;
            }else if(cmp == -1){
                parent = parent.right;
            }else{
                return parent;
            }
        }
        return null;
    }



    public Key select(int k){
        return (Key) select(root, k).key;
    }

    private Node select(Node node, int k){
        if(node == null) return null;
        int t = size(node.left);
        if(t > k) return select(node.left, k);
        else if (t < k) return select(node.right, k-t-1);
        return node;
    }


    public Node rank(int num){
        if(root == null) return null;
        if(num < 0 || num >= size(root)) return null;
        return rank(root, size(root) - size(root.left)-1, num);
    }

    public Node rank(Node node, int index, int num){
        if(index == num){ return node; }
        if(num > index){
            node = node.left;
            return rank(node, index + size(node.right) + 1, num);
        }else{
            node = node.right;
            return rank(node, index - size(node.left) - 1, num);
        }
    }


    public Node put(Key key, Value value){
        Node node = new Node(key, value, 1);
        if(root == null){
            root = node;
            root.n = 1;
            return node;
        }

        putV(root, node);
        return node;
    }

    private Node putV(Node parent, Node newNode){
        Node prev = null;
        while(parent != null){
            int cmp = parent.key.compareTo(newNode.key);
            parent.n += 1;
            prev = parent;
            if(cmp != -1){
                parent = parent.left;
            }else{
                parent = parent.right;
            }
        }

        if(prev != null){
            int cmp = prev.key.compareTo(newNode.key);
            if(cmp != -1){
                prev.left = newNode;
            }else{
                prev.right = newNode;
            }
        }
        return newNode;
    }


    private Node put(Node parent, Node newNode){
        if (parent == null){
            return newNode;
        }
        int cmp = parent.key.compareTo(newNode.key);
        if(cmp != -1){
            parent.left = put(parent.left, newNode);
        }else{
            parent.right = put(parent.right, newNode);
        }
        parent.n = size(parent.left) + size(parent.right) + 1;
        return parent;
    }

    public Node[] getReorderAsc(){
        i = 0;
        Node[] nodes = new Node[root.n];
        generator(nodes, root);
        return nodes;
    }

    private void generator(Node[] nodes, Node node) {
        if(node == null) return;
        generator(nodes, node.left);
        nodes[i++] = node;
        generator(nodes, node.right);
    }

    public Node[] getReorderDesc(){
        y = 0;
        Node[] nodes = new Node[root.n];
        generatorDesc(nodes, root);
        return nodes;
    }

    private void generatorDesc(Node[] nodes, Node node) {
        if(node == null) return;
        generatorDesc(nodes, node.right);
        nodes[y++] = node;
        generatorDesc(nodes, node.left);
    }

    private static class Node<Key extends Comparable<Key>, Value>{
        private Key key;

        private Value value;

        private int n;

        private Node left, right;

        public Node(Key key, Value value, int n){
            this.key = key;
            this.value = value;
            this.n = n;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", n=" + n +
                    '}';
        }
    }


    public int level(){
        return level(root);
    }

    private int level(Node node){
        if(node == null) return 0;
        return Math.max(level(node.left), level(node.right)) + 1;
    }


    public static void main(String[] args) {
        MyBinarySearchTree1<Integer, Integer> myBinarySearchTree1 = new MyBinarySearchTree1();
        myBinarySearchTree1.put(5, 5);
        myBinarySearchTree1.put(8, 8);
        myBinarySearchTree1.put(10, 10);
        myBinarySearchTree1.put(3, 3);
        myBinarySearchTree1.put(4, 4);
        myBinarySearchTree1.put(2, 2);
        myBinarySearchTree1.put(6, 6);
        myBinarySearchTree1.put(9, 9);
        myBinarySearchTree1.put(11, 11);

        Node node = myBinarySearchTree1.rank(2);
        System.out.println(node);

        Integer key = myBinarySearchTree1.select(1);
        System.out.println(key);

//      System.out.println(myBinarySearchTree1.root);

//      System.out.println(myBinarySearchTree1.find(5));

        Node[] nodes = myBinarySearchTree1.getReorderDesc();
        System.out.println(nodes);
        System.out.println(myBinarySearchTree1.level());
    }

}
